Computing Shortest Paths among Curved Obstacles in the Plane

摘要

A fundamental problem in computational geometry is to compute anobstacle-avoiding Euclidean shortest path between two points in the plane. Thecase of this problem on polygonal obstacles is well studied. In this paper, weconsider the problem version on curved obstacles, commonly modeled assplinegons. A splinegon can be viewed as replacing each edge of a polygon by aconvex curved edge (polygons are special splinegons). Each curved edge isassumed to be of O(1) complexity. Given in the plane two points s and t and aset of $h$ pairwise disjoint splinegons with a total of $n$ vertices, wecompute a shortest s-to-t path avoiding the splinegons, in$O(n+h\log^{1+\epsilon}h+k)$ time, where k is a parameter sensitive to thestructures of the input splinegons and is upper-bounded by $O(h^2)$. Inparticular, when all splinegons are convex, $k$ is proportional to the numberof common tangents in the free space (called "free common tangents") among thesplinegons. We develop techniques for solving the problem on the general(non-convex) splinegon domain, which also improve several previous results. Inparticular, our techniques produce an optimal output-sensitive algorithm for abasic visibility problem of computing all free common tangents among $h$pairwise disjoint convex splinegons with a total of $n$ vertices. Our algorithmruns in $O(n+h\log h+k)$ time and $O(n)$ space, where $k$ is the number of allfree common tangents. Even for the special case where all splinegons are convexpolygons, the previously best algorithm for this visibility problem takes$O(n+h^2\log n)$ time.